package fun.ticsmyc.graph;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-02-23 11:25
 */
public class 并查集 {

    private class Node{
        //Anythings here
    }

    /**
     * 基于Map实现
     */
    private class UnionFindSet{
        private Map<Node,Node> fatherMap;
        private Map<Node,Integer> sizeMap;

        public UnionFindSet(){
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
        }

        /**
         * 初始化并查集 ，每个node的father指向自己。
         * @param nodes
         */
        public void makeSets(List<Node> nodes) {

            fatherMap.clear();
            sizeMap.clear();
            for(Node node : nodes){
                fatherMap.put(node,node);
                sizeMap.put(node,1);
            }
        }

        /**
         * 递归寻找一个node所在set的代表结点
         * @param node
         * @return
         */
        public Node findHead(Node node){
            Node father = fatherMap.get(node);
            if(father!= node){
                father = findHead(father);
            }
            fatherMap.put(node,father);
            return father;
        }

        /**
         * 判断两个node是否在同一个set中。 (判断代表结点是否equal)
         * @param node1
         * @param node2
         * @return
         */
        public boolean isSameSet(Node node1, Node node2){
            return findHead(node1).equals(findHead(node2));
        }

        /**
         * 合并两个节点所在的Set
         * @param a
         * @param b
         */
        public void union(Node a , Node b){
            if(a==null || b==null){
                return;
            }
            Node aHead = findHead(a);
            Node bHead=findHead(b);
            if(aHead!=bHead){
                //合并
                if(sizeMap.get(aHead) > sizeMap.get(bHead)){
                    //b挂在a上
                    fatherMap.put(bHead,aHead);
                    sizeMap.put(aHead,sizeMap.get(aHead)+ sizeMap.get(bHead));
                }else{
                    fatherMap.put(aHead,bHead);
                    sizeMap.put(bHead,sizeMap.get(aHead)+ sizeMap.get(bHead));
                }
            }
        }
    }


    /**
        基于数组实现
     */
    private class UnionFind{
        int[] f;
        int[] rank;
        int n;

        public UnionFind(int n) {
            this.n = n;
        }

        public int find(int x){
            return f[x] ==x ? x : (f[x]=find(f[x]));
        }
        public boolean union(int x, int y){
            int fx =find(x);
            int fy = find(y);
            if(fx == fy){
                return false;
            }
            rank[fy] += rank[fx];
            f[fx] = fy;
            return true;
        }
        public boolean connect(int x, int y){
            return find(x) == find(y);
        }

    }
}
